import java.util.*;

public class TestBinaryTree {
    //孩子表示法实现二叉树
    static class TreeNode {
        //1.建立数据域、左孩子的引用和右孩子的引用
        public char val;
        public TreeNode left;//存储左孩子的引用
        public TreeNode right;//存储右孩子的引用

        public TreeNode(char val) {
            this.val = val;
        }
    }

    //开始创建二叉树
    public TreeNode createTree() {
        //2.创建二叉树的结点
        TreeNode treeNodeA = new TreeNode('A');
        TreeNode treeNodeB = new TreeNode('B');
        TreeNode treeNodeC = new TreeNode('C');
        TreeNode treeNodeD = new TreeNode('D');
        TreeNode treeNodeE = new TreeNode('E');
        TreeNode treeNodeF = new TreeNode('F');
        TreeNode treeNodeG = new TreeNode('G');
        TreeNode treeNodeH = new TreeNode('H');

        //3.有左孩子赋值到左边，有右孩子的赋值到右边并确定根节点
        treeNodeA.left = treeNodeB;
        treeNodeB.left = treeNodeD;
        treeNodeB.right = treeNodeE;
        treeNodeE.right = treeNodeH;
        treeNodeA.right = treeNodeC;
        treeNodeC.left = treeNodeF;
        treeNodeC.right = treeNodeG;
        return treeNodeA;//确定根节点
    }

    //前序遍历
    public void preOrder(TreeNode root) {
        //根节点为空
        if (root == null) {
            return;
        }
        //不为空
        System.out.print(root.val + " ");//打印此时根节点
        preOrder(root.left);//访问左边
        preOrder(root.right);//访问右边
    }

    //中序遍历
    public void inOrder(TreeNode root) {
        //根节点为空
        if (root == null) {
            return;
        }
        //不为空
        inOrder(root.left);//访问左边
        System.out.print(root.val + " ");//打印此时根节点
        inOrder(root.right);//访问右边
    }

    //后序遍历
    public void postOrder(TreeNode root) {
        //根节点为空
        if (root == null) {
            return;
        }
        //不为空
        postOrder(root.left);//访问左边
        postOrder(root.right);//访问右边
        System.out.print(root.val + " ");//打印此时根节点
    }

    //求二叉树的结点个数
    //1.遍历的思路
    public static  int nodeSize = 0;//计数器
    public int size(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        nodeSize++;
        size(root.left);//访问左边
        size(root.right);//访问右边
        return nodeSize;//返回计数器的值
    }

    //2.递归求解
    public int nodeSize(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        return nodeSize(root.left) + nodeSize(root.right) + 1;//左树加右树加1
    }

    //1.遍历获取二叉树的叶子结点个数
    public static int leafSize = 0;//叶子计数器
    public int getLeafNodeCount(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空 - 两个都为空即是叶子
        if (root.left == null && root.right == null) {
            leafSize++;//叶子个数加1
        }
        //调用方法访问左孩子和右孩子
        getLeafNodeCount(root.left);
        getLeafNodeCount(root.right);
        return leafSize;//返回叶子个数
    }

    //2.递归获取叶子结点个数
    public int leafNodeSize(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        if (root.left == null && root.right == null) {
            return 1;//叶子结点数
        }
        //左边的叶子和右边的叶子相加
        return leafNodeSize(root.left) + leafNodeSize(root.right);
    }

    //递归实现获取第k层的节点个数
    public int getKLevelNodeCount(TreeNode root, int k) {
        //不能为空，层数不能是0或者负数
        if (root == null || k <= 0) {
            return 0;
        }
        //k是第一层的情况
        if (k == 1) {
            return 1;//直接返回1
        }
        //大于1的情况 - 左树的k-1层加上右数的k-1层
        return getKLevelNodeCount(root.left, k - 1) + getKLevelNodeCount(root.right, k - 1);
    }

    //递归实现获取二叉树的高度
    public int getHeight(TreeNode root) {
        //为空
        if (root == null) {
            return 0;
        }
        //不为空
        int leftHeight = getHeight(root.left);//求左树的高度
        int rightHeight = getHeight(root.right);//求右树的高度
        //返回左右树的最大值加1
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    //递归查找val值是否存在
    public TreeNode findVal(TreeNode root, char val) {
        //为空
        if (root == null) {
            return null;
        }
        //不为空的情况
        //根节点此时的值等于我要查找的值
        if (root.val == val) {
            //返回此时root的地址
            return root;
        }
        //root此时的值不等于我要查找的值 - 调用方法访问左右两边的值
        TreeNode leftVal = findVal(root.left, val);//访问左边
        //此时左边的值不为空就继续找
        if (leftVal != null) {
            return leftVal;
        }
        TreeNode rightVal = findVal(root.right, val);//访问右边
        //此时右边的值不为空就继续找
        if (rightVal != null) {
            return rightVal;
        }
        //整个树都访问完了就说明没有val值
        return null;
    }

    //非递归实现层序遍历
    public void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //不为空 - 实现队列
        Queue<TreeNode> queue = new LinkedList<>();
        //压入元素到队列中
        queue.offer(root);
        //队列不为空
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();//弹出给cur
            //同时打印队头的元素
            System.out.print(cur.val + " ");
            //如果cur的左边不是空的说明未遍历结束
            if (cur.left != null) {
                //继续压入元素到队列中
                queue.offer(cur.left);
            }
            //如果cur右边不是空的说明未遍历结束
            if (cur.right != null) {
                //继续压入
                queue.offer(cur.right);
            }
        }
    }

    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        //为空的情况
        if (root == null) {
            return true;//是完全二叉树
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);//将此时root结点放到队列中
        //队列不为空
        while (!queue.isEmpty()) {
            //弹出此时队列的队头元素
            TreeNode cur = queue.poll();
            //压入root的左和右
            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        //判断队列剩下的值是否有非null的数据
        while (!queue.isEmpty()) {
            TreeNode popValue = queue.poll();//弹出此时队头的元素
            //如果队列中有非null的元素则不是完全二叉树
            if (popValue != null) {
                return false;
            }
        }
        //若循环结束说明都为空 - 即是完全二叉树
        return true;
    }

    public static void main(String[] args) {
        TestBinaryTree testBinaryTree = new TestBinaryTree();
        TestBinaryTree.TreeNode root = testBinaryTree.createTree();//调用创建二叉树

        //测试前序遍历
        testBinaryTree.preOrder(root);
        System.out.println();//换行
        //测试中序遍历
        testBinaryTree.inOrder(root);
        System.out.println();//换行
        //测试后续遍历
        testBinaryTree.postOrder(root);
        System.out.println();

        testBinaryTree.size(root);
        System.out.println("结点个数：" + TestBinaryTree.nodeSize);//测试遍历求树的节点个数
        System.out.println("结点个数：" + testBinaryTree.nodeSize(root));//测试递归求树的结点个数

        testBinaryTree.getLeafNodeCount(root);
        System.out.println("叶子数：" + TestBinaryTree.leafSize);//测试遍历获取叶子数
        System.out.println("叶子数：" + testBinaryTree.leafNodeSize(root));//测试递归获取叶子数
        System.out.println("第1层的结点个数：" + testBinaryTree.getKLevelNodeCount(root, 1));//测试获取k层结点个数
        System.out.println("第2层的结点个数：" + testBinaryTree.getKLevelNodeCount(root, 2));//测试获取k层结点个数
        System.out.println("第3层的结点个数：" + testBinaryTree.getKLevelNodeCount(root, 3));//测试获取k层结点个数
        System.out.println("第4层的结点个数：" + testBinaryTree.getKLevelNodeCount(root, 4));//测试获取k层结点个数

        //测试获取二叉树的高度
        System.out.println("二叉树高度：" + testBinaryTree.getHeight(root));
        //测试查找val值
        System.out.println("val：" + testBinaryTree.findVal(root, 'H'));

        //测试层序遍历
        System.out.println("层序遍历：");
        testBinaryTree.levelOrder(root);

        //测试判断是不是完全二叉书
        System.out.println();
        System.out.println(testBinaryTree.isCompleteTree(root));
    }
}

